
\chapter{Virtual Memory System}

The virtual memory system\index{vmm } allows the matrix
elements to be stored outside of RAM. The external file may
be stored on a hard drive, floppy drive, or in a RAM disk.
The RAM disk provides the fastest access to the matrices,
but may be of little value to machines without a large
amount of extended memory. The matrix class stores at most
64 doubles in a buffer in RAM. If the requested element is
not in the buffer, then the virtual system searches the
file for the block containing the element. The virtual
system then pages the requested block into the matrix
buffer.

The algorithm for allocating memory is found in Kernighan
and Ritchie\cite{kr:cprg}. Holub\cite{Ho:pr} adapted the
algorithm for managing the data in virtual memory file
(instead of data on the heap). Holub's program was
modified to compile in Turbo C++, and some bugs were
corrected. Holub then constructed a class for integer
vectors stored in virtual memory. This class was adapted to
doubles, and the matrix class was constructed by
dereferencing matrix elements stored in the virtual vector
in row major order. The matrix class, VMatrix, will be
described later. 

This chapter will give a loose explanation of the virtual
memory system. It will concentrate on the public functions
in Holub's work. The reader who is interested in using
these functions should obtain a copy of the article, and
work through the program \footnote{Type it in and
comprehend the comments. I took three weeks of spare
time.}. There are some sparks in it.

However, these functions are fragile, so it is not
recommended that they be used directly in any program for
the virtual matrix applications. The virtual memory
functions should be considered encapsulated in the matrix
algorithms. The matrix class frees the user of the overhead
of directly manipulating the virtual memory.

If you are using the in-ram version, you can skip this chapter
since matrices are allocated from the heap using calloc().

\section{vmem and hdr}

The virtual memory system (vmm) is driven off the following
two structures:

\begin{verbatim}
typedef struct vmem{
  unsigned signature;
  unsigned dirty;
  unsigned ele_size;
  unsigned ele_per_blk;
  long num_ele;
  unsigned cblock;
  char *buf;
} vmem;

typedef struct hdr {
  int active;
  int nrefs;
  unsigned nblocks;
  unsigned offset;
  union { struct hdr *h; //if hdr is in freelist (active=0)
        struct vmem *v;  //virt. mem. element (active = 1)
  } next;
} hdr;

\end{verbatim}

It helps to think of the virtual memory file as a long
array of unsigned chars. The hdr structure points to a
region in the file. The region may be used or free for use.
The used regions of the file are referenced by a vmem
structure. The unused regions are kept in a circular linked
list of headers. These structures are described in Kernighan
and Ritchie. The elements of the hdr structure are:
\begin{description}
  \item[active] An indicator that the header points to a
                vmem (1) or is in the freelist (0). It is
                used for error trapping and debugging.
  \item[nrefs] Indicator for the number of matrices using 
                this hdr. See the chapter on the stack for
                how this variable is used.  
  \item[nblocks] number of blocks pointed to by the hdr
  \item[offset]  the offset in the virtual file of the
                 first block pointed to. 
  \item[next]  The next header in the freelist, or the vmem
               being pointed to
\end{description}
The hdr is analogous to a pointer returned by malloc() of
freed by free().

The vmem structure contains the information for an active
hdr. The vmm file is organized in blocks of size
BLK\_SIZE. \footnote{The block size is 512 for a VMatrix.
This allows a 32 meg memory buffer}
The elements of the vmem are:
\begin{description}
  \item[signature] an indicator that the matrix has not
                   been corrupted by heap overwrites. It
                   is 0x5a5a when active, and set to zero
                   when it is freed. This leaves a zero on
                   the heap in case the freed pointer is referenced.
  \item[dirty] An indicator that an element in the page
               buffer has been changed. If this flag is
               set, then write the buffer out to disk
               before reading in a new page.
  \item[ele\_size] size in bytes of an element being stored
  \item[ele\_per\_block] number of elements per block
  \item[num\_ele] number of elements pointed to
  \item[cblock] block currently in buffer
  \item[buf] a pointer to the page buffer.
\end{description}

The function vmalloc() creates a hdr and a vmem. The
function vfree() frees the vmem and places the hdr in the
freelist. Freed space in the file is coalesced with
neighboring free blocks.   

\section{vopen() and vclose()}

The function vopen()\index{vmm!vopen()} initializes the vmm
system. The file \$\$\$\$vmem.tmp is created on a disk.
This is the temporary memory file where the matrices are
stored in row major order. You can specify the disk for
opening the file on through the environment variable
TMP\index{YAMP!TMP}. Use the DOS command \verb+ SET TMP=D:+
before running your YAMP program.  This will tell the
program to use the D drive for the virtual file. The
current disk is used if you do not use the environment
variable. If you use a RAM disk, then the paging scheme is
reasonably fast. There is a performance penalty for using a
physical disk. Note that the vmm file can grow as large as
32 megabytes, so your decision to use a RAM disk hinges on
the space requirements of your application.  There can be
at most 65536 blocks, each at 512 bytes, so there can be at
most 33,554,432 bytes (or 32,768 Kbytes) in
\$\$\$\$vmem.tmp.

vopen()\index{vmm!vopen()} is called when the first virtual
matrix is constructed, so it does not need to be called for
the matrix application.

vclose()\index{vmm!vclose()} closes the virtual memory file and
shuts down the virtual memory pointers. This function
should be called before exiting the program. If vclose() is
not called, \$\$\$\$vmem.tmp is not deleted from the disk.

\section{vmalloc() and vfree()}

vmalloc()\index{vmm!vmalloc()} and vfree()\index{vmm!vfree()}
allocate and free memory from \$\$\$\$vmem.tmp. The analogous
functions in C are malloc() and free(). vmalloc() returns a
void hdr, which can be cast. vfree() frees the memory, but
returns a 1 on error and sets an error message number. This
differs from free() which is a returns no value. 

The algorithms of these functions are difficult to explain,
so the reader is referred to Holub\cite{Ho:pr} and
Kernighan and Ritchie\cite{kr:cprg}. Tondo and
Gimpel\cite{tg:answ} also offer some insight into the
problem. The basic idea behind vmalloc() is to
search the free list for a set of blocks large enough to
fulfill the request. If one is not found, the
\$\$\$\$vmem.tmp grows. The basic idea behind vfree() is to
delete the vmem structure and place the hdr in the
freelist. Space around the freed blocks is coalesced. This
helps reduce checker-boarding of the memory. Data is stored
in contiguous blocks.

\section{vread() and vwrite()}

vread()\index{vmm!vread()} accesses the virtual array
element.  The prototype is void "*vread(hdr *p, long index)".
The hdr pointer, p, is the virtual array. The function thus
may be thought of as reading p[index]. The block number for
p[index] is calculated. If that block is not in the buffer,
and the buffer is dirty, the buffer is written back to disk
before the requested block is read.

vwrite()\index{vmm!vwrite()} writes data out to
\$\$\$\$vmem.tmp at the indicated hdr and index. 

Neither of these functions should be called in a YAMP
program since these functions are encapsulated in the
virtual vectors and matrices.